package sort;

import java.util.Arrays;

public class MergeSort implements Sort {
    @Override
    public void sort(int[] arr, boolean asc) {
        int len;
        if ((len = arr.length) == 1) {
            return;
        }
        int mid = len / 2;
        int[] left = Arrays.copyOf(arr, mid);
        int[] right = Arrays.copyOfRange(arr, mid, len);
        sort(left, asc);
        sort(right, asc);

        int[] mergeRes = merge(left, right, asc);
        System.arraycopy(mergeRes, 0, arr, 0, len);

    }

    private int[] merge(int[] left, int[] right, boolean asc) {
        int len1 = left.length, len2 = right.length;
        int[] newArr = new int[len1 + len2];
        int idx = 0, idx1 = 0, idx2 = 0;
        while (idx1 < len1 && idx2 < len2) {
            if ((asc && left[idx1] < right[idx2]) || (!asc && left[idx1] > right[idx2])) {
                newArr[idx++] = left[idx1++];
            } else {
                newArr[idx++] = right[idx2++];
            }
        }

        while (idx1 < len1) {
            newArr[idx++] = left[idx1++];
        }
        while (idx2 < len2) {
            newArr[idx++] = right[idx2++];
        }
        return newArr;
    }
}
